Search for: All records

An important question in elections is determining whether a candidate can be a winner when some votes are absent. We study this determining winner with absent votes (WAV) problem with elections that take top-truncated ballots. We show that the WAV problem is NP-complete for single transferable vote, Maximin, and Copeland, and propose a special case of positional scoring rule such that the problem can be computed in polynomial time. Our results for top-truncated rankings differ from the results in full rankings as their hardness results still hold when the number of candidates or the number of missing votes are bounded, while we show that the problem can be solved in polynomial time in either case. 

Algorithms are used to aid decision-making for a wide range of public policy decisions. Yet, the details of the algorithmic processes and how to interact with their systems are often inadequately communicated to stakeholders, leaving them frustrated and distrusting of the outcomes of the decisions. Transparency and accountability are critical prerequisites for building trust in the results of decisions and guaranteeing fair and equitable outcomes. Unfortunately, organizations and agencies do not have strong incentives to explain and clarify their decision processes; however, stakeholders are not powerless and can strategically combine their efforts to push for more transparency. In this paper, I discuss the results and lessons learned from such an effort: a parent-led crowdsourcing campaign to increase transparency in the New York City school admission process. NYC famously uses a deferred-acceptance matching algorithm to assign students to schools, but families are given very little, and often wrong, information on the mechanisms of the system in which they have to participate. Furthermore, the odds of matching to specific schools depend on a complex set of priority rules and tie-breaking random (lottery) numbers, whose impact on the outcome is not made clear to students and their families, resulting in many “wasted choices” on students’ ranked lists and a high rate of unmatched students. Using the results of a crowdsourced survey of school application results, I was able to explain how random tie-breakers factored in the admission, adding clarity and transparency to the process. The results highlighted several issues and inefficiencies in the match and made the case for the need for more accountability and verification in the system. 

Data is becoming increasingly personal. Individuals regularly interact with a wide variety of structured data, from SQLite databases on phones, to HR spreadsheets, to personal sensors, to open government data appearing in news articles. Although these workloads are important, many of the classical challenges associated with scale and Big Data do not apply. This panel brings together experts in a variety of fields to explore the new opportunities and challenges presented by "Small Data".